/**
 * 1011. 在 D 天内送达包裹的能力
 * https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
 */
public class Solutions_1011 {
    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int D = 5;  // output: 15

//        int[] weights = {3, 2, 2, 4, 1, 4};
//        int D = 3;  // output: 6

//        int[] weights = {1, 2, 3, 1, 1};
//        int D = 4;  // output: 3

        int result = shipWithinDays(weights, D);
        System.out.println(result);
    }

    public static int shipWithinDays(int[] weights, int D) {
        // 最少的运送能力 min = weights 中的最大值
        // 最多的运送能力 max = weights 的总和
        // 即要使 min 尽可能地大
        int min = 0, max = 0;
        for (int weight : weights) {
            min = Math.max(min, weight);
            max += weight;
        }
        if (D == 1) {
            // 要求一趟运送完，那么一趟运送 max 的重量
            return max;
        } else if (D == weights.length) {
            // 要求 weights.length 趟运送完，那么一趟最少运送 min 的重重
            return min;
        }
        while (min < max) {
            // 二分法，得到 min 和 max 的中间值
            int mid = min + (max - min) / 2;
            int needDay = 1;
            int w = 0;
            // 遍历 weights，计算出载重为 mid 时，共需要 needDay 天
            for (int weight : weights) {
                w += weight;
                if (w > mid) {
                    needDay ++;
                    w = weight;
                }
            }
            // 原本要 5 天，但是 3 天就完成了，那么尝试将 mid 再缩小点（即 max 缩小）
            if (needDay <= D) {
                max = mid;
            } else {
                // 原本要 5 天，但是 8 天才能完成，那么尝试将 mid 再扩大点（即 min 扩大）
                min = mid + 1;
            }
        }
        return min;
    }
}
